//
// Created by PC on 2024/5/17.
//大整数的因子
// OJ:https://oj.youdao.com/problem/9048?from=problems pass
// OJ:http://ybt.ssoier.cn:8088/problem_show.php?pid=1171 pass
/*
 * 1171：大整数的因子

时间限制: 1000 ms         内存限制: 65536 KB
【题目描述】
已知正整数k 满足2≤k≤9，现给出长度最大为30位的十进制非负整数c，求所有能整除c的k
【输入】
一个非负整数c，c的位数≤30
【输出】
若存在满足 c%k == 0 的k ，从小到大输出所有这样的k，相邻两个数之间用单个空格隔开；若没有这样的k ，则输出"none"。
【输入样例】
30
【输出样例】
2 3 5 6
 * */
// 被7整除判断 掐掉后三位再减去掐掉的数字


#include <iostream>

using namespace std;

bool divideBySeven(string s)
{
    // t1是掐掉后剩下的数字 t2是掐掉的三位数字
    while (s.size() >= 9)
    {
        string t1, t2;
        int i = 0;
        for (; i < s.size() - 3; ++i)
        {
            t1 += s[i];
            // 先给t2前边补零, 让t1和t2长度相等
            if (i > 2)
                t2 += "0";
        }
        for (; i < s.size(); ++i)
            t2 += s[i];
//        cout<<t1<<' '<<t2<<endl;
        // s = t1 - t2
        int l[t1.size()] = {0};
        // 逐位相减 存对应到l[]中
        for (int i = 0; i < t1.size(); ++i)
            l[i] = t1[i] - '0' - (t2[i] - '0');
        s = "";
        for (int j = t1.size() - 1; j >= 0; --j)
        {
            if (l[j] < 0)
            {
                l[j] += 10;
                l[j - 1] -= 1;
            }
            s = to_string(l[j]) + s;
        }
    }
    if (s.size() < 9)
    {
        int num = stoi(s);
        if (num % 7 == 0)
            return true;
    }

    return false;
}

int main()
{
    string n = "35";
    n = "4973545080000"; //2 3 4 5 6 7 8 9
//    n = "89878728536670772460703949360"; //2 4 5 8
//    n = "43159958401976851050493488739"; // none
//    n = "97352064275798174864936464204"; // 2 4
//    n = "75068252038625104240475771220"; // 2 3 4 5 6
//    cin>>n;
    int last_one = n[n.size() - 1] - '0';
    int last_two,last_three;
    if (n.size() > 1)
        last_two = n[n.size() - 2] - '0';
    else
        last_two = 0;
    if (n.size()>1)
        last_three = n[n.size()-3]-'0';
    else
        last_three=0;
    int total = 0;
    for (int i = 0; i < n.size(); ++i)
    {
        total += (n[i] - '0');
    }
    bool allNot = true;
    if (last_one % 2 == 0)
    {
        cout << 2 << ' ';
        allNot = false;
    }
    if (total % 3 == 0)
    {
        cout << 3 << ' ';
        allNot = false;
    }
    if ((last_one + last_two * 10) % 4 == 0)
    {
        cout << 4 << ' ';
        allNot = false;
    }
    if (last_one % 5 == 0 || last_one == 0)
    {
        cout << 5 << ' ';
        allNot = false;
    }
    if (last_one % 2 == 0 && total % 3 == 0)
    {
        cout << 6 << ' ';
        allNot = false;
    }
    if ( divideBySeven(n) )
    {
        cout << 7 << ' ';
        allNot = false;
    }
    if ((last_one + last_two * 10 + last_three*100) % 8 == 0)
    {
        cout << 8 << ' ';
        allNot = false;
    }
    if (total % 9 == 0)
    {
        cout << 9;
        allNot = false;
    }
    if (allNot)
        cout<<"none";
    return 0;
}